if (!window.trace)
	var trace = function(x) {
		document.write('<pre style="font:11px monospace; background-color:#eee;padding:3px;margin:5px 0;">' + html_escape(sprintf.apply(this, arguments)) + '</pre>');
	};


var yy_ec = [];
var yy_ec_char_codes = {};
var last_ec = 0;
var get_ec = function(c, def) {
	var code = c.charCodeAt(0);
	var ec = yy_ec[code];
	if (!ec) {
		if (def !== undefined)
			return def;
		ec = yy_ec[code] = ++last_ec;
		yy_ec_char_codes[c] = ec;
	}
	return ec;
};


var Stream = function(str) {
	if (str !== undefined)
		this.load(str);
};
Stream.prototype = {
	EOF: -1,
	load: function(str) {
		this.source = str;
		this.length = this.source.length;
		this.reset();
	},
	eof: function() {
		return this.char === this.EOF;
	},
	reset: function() {
		this.pos = 0;
	},
	getch: function() {
		if (this.pos >= this.length)
			return this.char = this.EOF;
		return this.char = this.source[this.pos++];
	},
	rewind: function(n) {
		this.pos -= n;
	}
};

var last_rule_id = 1;

var lex_rule = function(str, f) {
	var out = [];
	var i, max = str.length;
	for (i = 0; i < max; ++i)
		out[i] = {};
	//var action = function() { f(str) };
	var action = f;
	//action.toString = function() { return '[' + str + ']' };
	out[out.length] = { action: action };
	for (i = 0, max = out.length - 1; i < max; ++i)
		out[i][str[i]] = out[i + 1];
	return out[0];
};


var lex_get_assoc = function(s) {
	var objs = [];
	var rec = function(s) {
		if (s.chars)
			return s.chars;
		var c, code, n;
		s.chars = {};
		objs[objs.length] = s;
		if (s.action)
			s.chars.action = s.action;
		if (s.nxt && s.nxt.length > 0) {
			if (s.nxt[0])
				s.chars['.'] = rec(s.nxt[0]);
			for (c in yy_ec_char_codes) {
				code = yy_ec_char_codes[c];
				n = s.nxt[code];
				if (!n) continue;
				s.chars[c] = rec(n);
			}
		}
		return s.chars;
	};
	var chars = rec(s, '');
	for (var i = 0; i < objs.length; ++i)
		delete objs[i].chars;
	return chars;
};


var lex_merge = function(r1, r2, d) {
	if (!d) d = 0;
	
	if (r1.action)
		return r1;
	
	if (r2.action && !r1.action) {
		r1.action = r2.action;
	}

	var i;

	if (!r1.nxt)
		r1.nxt = [];

/*
	var log = [];
	log[log.length] = dump(lex_get_assoc(r1), 'r1');
	log[log.length] = dump(lex_get_assoc(r2), 'r2');
	trace(sprintf('\
		<table cellpadding=5 style="padding-left:%dpx;width:100%;border-spacing:0;">\
			<tr>\
				<td valign=top style="border-right:3px solid red">%s\
				<td valign=top>%s\
		</table>\
	', d*40, log[0], log[1]));
/**/

	if (r2.nxt) {
		for (i = 1; i < r2.nxt.length; ++i) {
			if (!r2.nxt[i]) continue;
			if (!r1.nxt[i])
				r1.nxt[i] = r2.nxt[i];
			else
				lex_merge(r1.nxt[i], r2.nxt[i], d+1);
		}


		if (r2.nxt[0]) {
			if (!r1.nxt[0])
				r1.nxt[0] = r2.nxt[0];
			/*
			for (i = 1; i < Math.max(1, r1.nxt.length); ++i) {
				if (!r1.nxt[i])
					r1.nxt[i] = r2.nxt[0];
				//else
				//	lex_merge(r1.nxt[i], r2.nxt[0]);
			}
			*/
		}
	}

	//alert(dump(r1));

/*
	//log[log.length] = dump(r1, 'result');
	trace(sprintf('\
		<div style="margin-top:-50px; margin-left:%dpx;margin-bottom:10px;border-spacing:0">\
			%s\
		</div>\
	', d*40, dump(lex_get_assoc(r1), 'result')));
/**/
		
	return r1;
};


var create_lexbuf = function(l) {
	return {
		initial: l,
		pos: 0,
		state: l,
		last_accepting_pos: 0,
		last_accepting_state: null,
		buf: ''
	}
};

var lex = function(lexbuf, input) {
	/*
	lexbuf.initial
	lexbuf.pos
	lexbuf.state
	lexbuf.last_accepting_pos
	lexbuf.last_accepting_state
	lexbuf.yytext
	*/
	var lex_empty_action = window.lex_empty_action;
	var yy_ec = window.yy_ec;
	
	if (input != undefined)
		lexbuf.buf += input;

	var max = lexbuf.buf.length;
	var c;
	var cnt = 0, cnt2 = 0;
	var i = lexbuf.pos;
	var s, state = lexbuf.state;
	var _yytext = lexbuf.yytext || '';
	
	while (true) {
		if (cnt++ > 1000000) { alert('hang up'); return; }
		if (i >= max) break;
		c = lexbuf.buf[i];

		last_accepting_pos = -1;

		while (state.nxt && (s = state.nxt[yy_ec[(c = lexbuf.buf[i]).charCodeAt(0)] || 0] )) {
			++cnt2;
			state = s;
			_yytext += c;
			++i;
			if (state.action) {
				last_accepting_state = state;
				last_accepting_pos = i;
			}
			if (i >= max)
				break;
		}
		
		if (!state.action) {
			if (last_accepting_pos < 0) {
				alert('STOP at position ' + i + ' near "' + lexbuf.buf.substr(i, 10) + '..."');
				return;
			}
			_yytext = _yytext.substr(i - last_accepting_pos - 1);
			state = last_accepting_state;
			i = last_accepting_pos;
		}
		
		if (state.action && state.action !== lex_empty_action) {
			//window.yytext = _yytext;
			x = state.action(_yytext);

			/*
			lexbuf.buf = lexbuf.buf.substr(last_accepting_pos);
			max -= last_accepting_pos;
			i -= last_accepting_pos;
			*/
			
			last_accepting_pos = 0;
			lexbuf.pos = i;
			
		}
		state = lexbuf.initial;
		_yytext = '';
	}
	lexbuf.yytext = _yytext;
	lexbuf.state = state;
	lexbuf.pos = i;
	lexbuf.last_accepting_state = last_accepting_state;
	lexbuf.last_accepting_pos = last_accepting_pos;
	
	return lexbuf;
};


var add_range = function(assoc, start, end) {
	var c;
	for (var i = start.charCodeAt(0), max = end.charCodeAt(0); i <= max; ++i) {
		c = String.fromCharCode(i);
		//c = get_ec(c);
		assoc[c] = 1;
	}
	return assoc;
};

var parse_range = function(stream) {
	var c, c0;
	var assoc = {};

stream_loop:	
	while (true) {
		c = stream.getch();
		if (stream.eof())
			break;
		switch (c) {
			case ']':
				break stream_loop;
			default:
				assoc[c] = 1;
				break;
			case '.':
				assoc.any = 1;
				break;
			case '-':
				if (c0 === undefined) {
					assoc[c] = 1;
				} else {
					c = stream.getch();
					add_range(assoc, c0, c);
				}
				break;
			case '\\':
				c = stream.getch();
				switch (c) {
					case 'w':
						add_range(assoc, 'a', 'z');
						add_range(assoc, 'A', 'Z');
						add_range(assoc, 'а', 'я');
						add_range(assoc, 'А', 'Я');
						assoc['_'] = 1;
						//add_range(assoc, 'A', 'Z');
						break;
					case 'd': add_range(assoc, '0', '9'); break;
					case 's': assoc[' '] = assoc['\t'] = 1; break;
					case 't': assoc['\t'] = 1; break;
					case 'n': assoc['\n'] = 1; break;
					case 'r': assoc['\r'] = 1; break;
					default: assoc[c] = 1; break;
				}
				break;
		}
		c0 = c;
	}
	var out = [];
	for (var i in assoc)
		if (assoc[i] == 1)
			out[out.length] = get_ec(i);
	out.sort();
	return out;
	
	//throw "']' expected in regexp";
};


// asdfjkjkjkjkjretjfoeijccimwieorumwerwerieriweur

var parse_re = function(source) {
	var group = 0;
	var rec = function(stream, result) {
		var c = stream.getch();
		switch (c) {
			case stream.EOF:
				return result;
			default:
				c = get_ec(c);
				result.push(['C', c]);
				return rec(stream, result);
			case '\\':
				c = stream.getch();
				switch (c) {
					case 'w': result.push(['R', parse_range(new Stream('a-zA-Z_а-яА-Я'))]); break;
					case 'd': result.push(['R', parse_range(new Stream('0-9'))]); break;
					case 's': result.push(['R', parse_range(new Stream(' \t'))]); break;
					case 'r': result.push(['C', get_ec('\r')]); break;
					case 'n': result.push(['C', get_ec('\n')]); break;
					case 't': result.push(['C', get_ec('\t')]); break;
					default:  result.push(['C', get_ec(c)]); break;
				}
				return rec(stream, result);
			case '|':
				var x = rec(stream, []);
				return [['|', result, x]];
			case '[':
				if (stream.getch() == '^') {
					var r = parse_range(stream);
					result.push(['NR', r]);
				} else {
					stream.rewind(1);
					var r = parse_range(stream);
					result.push(['R', r]);
				}
				return rec(stream, result);
			case '(':
				var g = ++group;
				var x = rec(stream, []);
				result.push(['G', x, g]);
				return rec(stream, result);
			case ')':
				//return result.length == 1 ? result[0] : result;
				return result;
			case '?':
				var x = result.pop();
				if (x[0] == '*' || x[0] == '+')
					result.push([x[0] + '?', x[1]]);
				else
					result.push(['?', [x]]);
				return rec(stream, result);
			case '+':
				result.push(['+', [result.pop()]]);
				return rec(stream, result);
			case '*':
				result.push(['*', [result.pop()]]);
				return rec(stream, result);
			case '.':
				result.push(['.']);
				return rec(stream, result);
		}
	};
	if (source.constructor === RegExp)
		source = source.source;
	//alert(source);
	var stream = new Stream(source);
	var result = rec(stream, []);
	result.source = source;
//	trace(result);
	//dump_config({html:false});
	//alert(dump(result));
	//alert('<' + result[0][1] + '>');
	return result;
};

var lex_empty_action = function(){ };

var lex_re = function(re, action) {
	if (!action) action = lex_empty_action;
	
	if (re.constructor === RegExp)
		re = parse_re(re);
	
	var depth = 0;

	var rec = function(re, accept, g) {
		if (!re.length)
			return accept;			
		var hd = re[0];
		var tl = re.slice(1);
		
		var n = rec(tl, accept, g);
		
		while (hd.length == 1 && is_array(hd[0]))
			hd = hd[0];

		switch (hd[0]) {
			case 'R':
				//alert(hd[1]);
				var x = { nxt: [] };
				var cc = hd[1];
				for (var i = 0, max = cc.length; i < max; ++i)
					x.nxt[cc[i]] = n;
				return x;

			case 'NR':
				//alert(hd[1]);
				var x = { nxt: [] };
				var cc = hd[1];
				var i;
				//x.nxt[2] = n;
				for (i = 0; i <= last_ec; ++i)
					x.nxt[i] = n;
				
				
				//alert(x.nxt[cc[0]]);
				
				for (i = 0, max = cc.length; i < max; ++i)
					x.nxt[cc[i]] = undefined;

				//alert(x.nxt[1]);

				return x;
				
			case 'G':
				var _g = hd[2];
				
				// делаем копию конечного состояния группы
				var m = {};
				objoin(m, n);
				//var m = n;

				var a = rec(hd[1], m, _g);
				return a;

			case 'C':
				var x = { nxt: [] };
				x.nxt[hd[1]] = n;
				//trace(hd);
				//x[hd[1]] = n;
				return x;

			case '.':
				var x = { nxt: [] };

				if (!last_ec)
					x.nxt[0] = n;
				else
					for (var i = 0; i <= last_ec; ++i)
						x.nxt[i] = n;

				return x;

			case '|':
				var a = rec(hd[1], n, g);
				var b = rec(hd[2], n, g);
				lex_merge(a, b);
				return a;

			case '+':
				var m = {}
				var a = rec(hd[1], m, g);
				lex_merge(m, a);
				lex_merge(m, n);
				return a;

			case '+?':
				var m = {}
				var a = rec(hd[1], m, g);
				lex_merge(m, n);
				lex_merge(m, a);
				return a;

			case '*?':
				var m = {};
				var a = rec(hd[1], m, g);
				lex_merge(m, n);
				lex_merge(a, n);
				return a;

			case '*':
				var m = {};
				var a = rec(hd[1], m, g);
				lex_merge(m, a);
				lex_merge(m, n);
				return m;

			case '?':
				var a = rec(hd[1], n, g);
				lex_merge(a, n);
				return a;
			}
	};
	action.toString = function(){ return re.source };
	var accept = { action: action };

	var _st = set_trace();
	set_trace(0);
	
	var x = rec(re, accept);
	
	set_trace(_st);
	
	return x;
};





var mklex = function(prog) {
	var i, j, p, re, l;
	for (i in prog) {
		p = prog[i];
		for (j = 0; j < p.length; ++j) {
			re = p[j][0];
			if (re.constructor !== RegExp)
				re = re_escape(re);
			p[j][0] = parse_re(re);
		}
	}
	for (i in prog) {
		p = prog[i];
		l = {};
		for (j = 0; j < p.length; ++j)
			lex_merge(l, lex_re(p[j][0], p[j][1]));
		lex_merge(l, lex_re(/./, lex_empty_action));
		prog[i] = l;
	}
	window.lexbuf = create_lexbuf();
	window.BEGIN = function(s){
		lexbuf.state = lexbuf.initial = prog[s];
	};
	if (prog.INITIAL)
		BEGIN('INITIAL');	
};

var yylex = function(str){
	lexbuf.buf += str;
	lex(lexbuf);
};




